Trong những năm đầu, Hồng Kông trở thành điểm nóng của cướp biển, kẻ trộm, buôn bán ma túy và buôn lậu, và cũng là nơi ẩn náu của những kẻ chạy trốn triều đình nhà Thanh. Hồng Kông lúc đó không có trật tự công cộng. Sau khi chỉ huy quân đội Anh là William Caine trở thành Chánh án đầu tiên tại đây vào ngày 30 tháng 4 năm 1841, ông đã cho dựng một khu để giam cầm những tên tội phạm bị bắt ở góc đường Bailey và Stanton. Khi tỷ lệ tội phạm tăng vọt, khu vực không đủ còn đủ các phòng giam nên Caine đã chỉ định địa điểm trên một con dốc ở con đường Old Bailey (hiện đối diện với nhà tù Victoria). Nó được hoàn thành vào ngày 9 tháng 8 cùng năm và được đặt tên là Victoria Gaol.[3] Victoria Gaol được cho là một trong những tòa nhà đầu tiên được người Anh dựng lên ở Hồng Kông kể từ giữa thế kỉ XIX,[4] là nhà tù chính và duy nhất của Hồng Kông cho đến năm 1937.[5] Mặt chính của nhà tù vẫn được giữ theo kiến trúc Victoria, được xây dựng chủ yếu bằng đá granit và gạch.

Trong suốt cuộc nổi dậy Thái Bình Thiên Quốc, một lượng lớn người tị nạn và binh lính Thái Bình Thiên Quốc đã đến Hồng Kông. Sự bùng nổ dân số đã đẩy tỷ lệ tội phạm tăng lên, với số lượng kẻ trộm bị bắt giữ và cướp biển tăng lên từng ngày. Do đó, các nhà tù ở đây dần trở nên quá tải. Để giải quyết tình hình, Chính phủ Hồng Kông bắt đầu mở rộng các công trình nhà tù ở phía đông đường Old Bailey (nay là nhà tù Victoria), và được hoàn thành vào năm 1858.[3] Nhưng nhà tù Victoria Gaol vẫn bị quá tải với số lượng tù nhân liên tục tăng, và chính quyền đã cho xây dựng một nhà tù mới trên đảo Stonecutter ngay ngoài khơi vào năm 1863, cho đến khi dự án bị hủy bỏ vào năm 1866.[6] Năm 1879, nhà tù không còn được quản lý bởi lực lượng cảnh sát. Năm 1899, Pháp lệnh Nhà tù được sửa đổi và năm sau nhà tù Victoria Gaol được đổi tên thành "Victoria Prison", để tưởng nhớ Nữ hoàng Victoria của Vương quốc Anh.[3][7]

Nhà tù dành cho phụ nữ Lệ Chi Giác (Lai Chi Kok) được mở cửa vào tháng 4 năm 1932, làm giảm bớt áp lực cho nhà tù Victoria. Sau khi hoàn thành nhà tù Hồng Kông tại Stanley (sau này gọi là nhà tù Stanley), nhà tù Victoria đã bị đóng cửa một thời gian. Tuy nhiên, nhà tù Stanley đã nhanh chóng trở nên quá tải và vào năm 1939, nhà tù Victoria đã mở cửa trở lại để giam giữ các tù nhân đang chờ xét xử. Trong Thế chiến II, nhà tù Victoria đã bị quân đội Nhật chiếm và sử dụng để bắt giam binh lính quân đội Anh và nhân viên của các lực lượng luật định gốc châu Âu. Hầu hết các cơ sở của nhà tù đã bị phá hủy bởi hỏa hoạn trong chiến tranh, và việc cải tạo lớn phải được thực hiện sau chiến tranh. Vào tháng 6 năm 1946, nhà tù Victoria được đổi tên thành "Victoria Remand Prison". Năm 1966, nó được đổi tên thành "Victoria Reception Centre" (Trung tâm tiếp nhận Victoria), nơi chứa các cá nhân đang chờ tuyên án, kháng cáo hoặc người chưa bị kết án. Một số tù nhân đang thụ án ngắn hơn cũng bị giam ở đây. Sau năm 1975, Hồng Kông chứng kiến số lượng lớn người tị nạn đến từ Việt Nam. Năm 1977, Trung tâm tiếp nhận Lệ Chi Giác đã được hoàn thành để thay thế các chức năng của Trung tâm tiếp nhận Victoria. Còn Trung tâm tiếp nhận Victoria đã được thay đổi để chứa các tù nhân đang chờ hồi hương hoặc trục xuất, và lại được đổi tên thành Victoria Prison.[8]

Vào ngày 8 tháng 9 năm 1995, nhà tù Victoria cùng với Trạm cảnh sát Trung khu và Toà án trung ương liền kề, được liệt kê là di tích pháp định của Hồng Kông.[2] Năm 1997 đánh dấu việc thành lập Đặc khu hành chính Hồng Kông thuộc Trung Quốc, đồng thời cũng kết thúc vấn đề về người di cư Việt Nam tại đây. Để đối phó với số lượng tù nhân nữ ngày càng tăng ở Hồng Kông, các phần của công trình đã được chuyển đổi để chứa tù nhân nữ trưởng thành kể từ tháng 1 năm 2001.[6]

Còn vào ngày 23 tháng 12 năm 2005, quyết định cuối cùng đã được đưa ra để đóng cửa nhà tù Victoria với nhóm tù nhân cuối cùng được phóng thích, chấm dứt vai trò của nhà tù như một cơ sở hình sự sau 165 năm phục vụ tại Hồng Kông. Nhà tù Victoria chính thức ngừng hoạt động vào ngày 12 tháng 3 năm 2006 và lần đầu tiên nhà tù được mở cửa cho công chúng vào tháng 3 năm 2006.[9]